<!-- 利用光线追踪技术实现万花筒效果 -->

<html>
<head>
<meta charset="UTF-8">
<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjs/5.4.0/math.min.js"></script>

<script>

	function unit_vector(vec) {
		return math.divide(vec, math.norm(vec))
	}
	
	
	/*
	* 计算一个随机的单位向量，该单位向量服从于特定的随机分布。
	*/
	function random_unit_vector() {
		const a = Math.random() * 2 * Math.PI;  // xy平面上的角度服从于均匀随机分布
		const z = Math.random() * 2 - 1;  // 高度服从均匀随机分布
		const r = math.sqrt(1 - z*z);          // 计算该高度下圆截面的半径
		return [r * math.cos(a), r * math.sin(a), z]
	}
	
	
	function reflect(vec, normal) {
		return math.subtract(vec, math.multiply(2, math.dot(vec, normal), normal))
	}


	/*
	* 计算从目标物体hitable射来的某个角度的光线所具有的颜色。
	* @param depth 指出这是第几次递归。递归次数超出限制则停止计算。
	*/
	function color(ray, hitable, depth) {
		let hit_record = hitable.hit(ray, 1e-12, Number.MAX_VALUE)
		if(hit_record) {
			const material = hit_record.material
			const res = material.scatter(ray, hit_record)
			if (depth < 50 && res) {
				const scattered = res['scattered']
				const attenuation = res['attenuation']
				return math.dotMultiply(attenuation, color(scattered, hitable, depth + 1))
			}
			return [1e-2, 1e-2, 1e-2]
		} else {
			const direction = ray.direction
			const t = math.multiply(0.5, direction[1] + 1)
			return math.add(math.multiply(1 - t, [1, 1, 1]), math.multiply(t, [0.5, 0.7, 1]))
		}
	}

    
    /*
    * 与color函数类似。不同之处在于，不仅计算了颜色信息，还记录了光线追踪的过程信息。
    */
	function colorWithRecord(ray, hitable, depth) {
        let hit_record = hitable.hit(ray, 1e-12, Number.MAX_VALUE)
        if (hit_record) {
        	const material = hit_record.material   
        	const res = material.scatter(ray, hit_record)
        	let record = {
        		"material":material,
        		"u": hit_record.u,
        		"v": hit_record.v,
        	}
        	if (depth < 50 && res) {
        		const scattered = res['scattered']
        		const attenuation = res['attenuation']
                const ret = colorWithRecord(scattered, hitable, depth + 1);
                const rgb = ret[0]; let records = ret[1];
                const rgb2 = math.dotMultiply(attenuation, rgb);
                records.push(record);
                return [rgb2, records];
        	}
        	return [[1e-2, 1e-2, 1e-2], []]
        }
        else {
        	const direction = ray.direction;
        	const t = math.multiply(0.5, direction[1] + 1);
        	return [
        	            math.add(math.multiply(1 - t, [1, 1, 1]), math.multiply(t, [0.5, 0.7, 1])),
        	           []
        	       ];
        }
	}


	class ImageTexture {
		constructor(imgId, scale) {
			this.scale = typeof(scale) === "undefined" ? 1.0 : scale;
			this.img = document.getElementById(imgId);
			this.width = this.img.width;
			this.height = this.img.height;
			// 只能通过canvas间接获取图像数据。有没有更好的方法呢？
			this.canvas = document.createElement('canvas');
			this.canvas.width = this.width;
			this.canvas.height = this.height;
			this.ctx = this.canvas.getContext('2d');
			this.ctx.drawImage(this.img, 0, 0);
			this._imgData = this.ctx.getImageData(0, 0, this.width, this.height)["data"];
		}

        /*
        * @param u 横坐标, 0<=u<=1
        * @param v 纵坐标, 0<=v<=1
        */
		at(u, v) {
			u = (u - 0.5) / this.scale + 0.5;
			v = (v - 0.5) / this.scale + 0.5;
			const defaultColor = [0, 0, 0];
			const row = parseInt(v * this.height);
			const col = parseInt(u * this.width);
			if (!(0 <= row && row < this.height && 0 <= col && col < this.width))
			    return defaultColor;
            const r = this._imgData[(row * this.width + col) * 4] / 255;
            const g = this._imgData[(row * this.width + col) * 4 + 1] / 255;
            const b = this._imgData[(row * this.width + col) * 4 + 2] / 255;
            return [r, g, b];
		}
	}
	
	
	// 散射体（材质）
	class Lambertian {
		/*
		* @param albedo 反射率
		* @param texture 纹理，可选
		*/
		constructor(a, texture) {
			this.albedo = a
			this.texture = texture
		}
		
		scatter(ray, hit_record) {
			const target = math.add(hit_record.point, hit_record.normal, random_unit_vector())
			const scattered = new Ray(hit_record.point, math.subtract(target, hit_record.point))
			let attenuation = this.albedo
			if (hit_record.u && hit_record.v && this.texture) {
				const rgb = this.texture.at(hit_record.u, hit_record.v);
                attenuation = math.dotMultiply(rgb, this.albedo);
			}
			return {
				'attenuation': attenuation,
				'scattered': scattered,
			}
		}
	}
	
	
	// 金属（材质）
	class Metal {
		constructor(a) {
			this.albedo = a
		}
		
		scatter(ray_in, hit_record) {
			const reflected = reflect(unit_vector(ray_in.direction), hit_record.normal)
			const scattered = new Ray(hit_record.point, reflected)
			const attenuation = this.albedo
			if (math.dot(scattered.direction, hit_record.normal) > 0)
				return {
					'attenuation': attenuation,
					'scattered': scattered
				}
			return null
		}
	}

	class Ray{
		constructor(origin, direction){
			this.origin = origin
			this.direction = unit_vector(direction)
		}

		point_at_t(t){
			return math.add(this.origin, math.multiply(this.direction, t))
		}
	}
	
	
	class Camera{
		constructor(){
			this.start = [-2, -1, -1]
			this.horizontal = [4, 0, 0]
			this.vertical = [0, 2, 0]
			this.origin = [0, 0, 0]
		}
		
		getRay(u, v) {
			return new Ray(this.origin, math.add(math.add(this.start, math.multiply(u, this.horizontal)), math.subtract(math.multiply(v, this.vertical), this.origin)))
		}
	}
	

	class Sphere{
		constructor(center, radius, material) {
			this.center = center
			this.radius = radius
			this.material = material
		}

		hit(ray, tmin, tmax) {
			const oc = math.subtract(ray.origin, this.center)
			const a = math.dot(ray.direction, ray.direction)
			const b = 2 * math.dot(oc, ray.direction)
			const c = math.dot(oc, oc) - this.radius**2
			const d = b**2 - 4 * a * c
			const material = this.material
			if (d > 0) {
				function record(parameter, center, radius) {
					if (parameter < tmax && parameter > tmin) {
						let point = ray.point_at_t(parameter)
						let hit_record = {
							t: parameter,
							point: point,
							normal: math.divide(math.subtract(point, center), radius),
							material: material
						}
						return hit_record
					}
					return null
				}
				let hit_record = record((-b - math.sqrt(d)) / 2 / a, this.center, this.radius)
				if(hit_record) return hit_record
				hit_record = record((-b + math.sqrt(d)) / 2 / a, this.center, this.radius)
				if(hit_record) return hit_record
			}
			return null
		}
	}

	/*
	* 一个三维空间中的二维矩形。
	*/
	class Rect{

		/*
		* 调用此构造函数，首先给出一个二维坐标系。坐标系由原点origin和x、y轴方向vx、vy指定。
		* 矩形的一个角位于坐标系原点，宽度方向平行于x轴，高度方向平行于y轴。矩形位于坐标系第一相限。
		* @param origin 矩形所在平面的原点
		* @param vx x轴方向
		* @param vy y轴方向
		* @param width 矩形的宽度
		* @param height 矩形的高度
		* @param material 材质
		*/
		constructor(origin, vx, vy, width, height, material) {
			this.origin = origin
			this.vx = unit_vector(vx)
			this.vy = unit_vector(vy)
			this.vz = math.cross(this.vx, this.vy)  // 矩形平面的单位法向量
			// 平面方程ax + by + cz + d = 0的各项系数是
			this.a = this.vz[0]; this.b = this.vz[1]; this.c = this.vz[2];
			this.d = -math.dot(this.vz, this.origin)
			this.width = width
			this.height = height
			this.material = material
		}

		hit(ray, tmin, tmax) {
			// 如果光线与平面法向量垂直，则不交
			if (math.abs(math.dot(this.vz, ray.direction)) < 1e-12)
				return null;
				
			// 求光线与平面的交点
			// 即求解t满足 this.vz.T * (ray.origin + ray.direction * t) + d = 0
			const t = -(this.d + math.dot(this.vz, ray.origin)) / math.dot(this.vz, ray.direction)
			
			if (t <= tmin || t >= tmax) // 超出限制
				return null
				
			const point = ray.point_at_t(t)
			const offset = math.subtract(point, this.origin)
			const px = math.dot(this.vx, offset)
			const py = math.dot(this.vy, offset)
			if (px < 0 || px > this.width || py < 0 || py > this.height)  // 超出矩形框
				return null
			
			// 击中
			// 根据入射光线决定法向量的方向，使得两面都能反射
			const normal = math.dot(this.vz, ray.direction) < 0 ? this.vz : math.unaryMinus(this.vz)
			const hit_record = {
				t: t,
				point: point,
				normal: normal,
				material: this.material,
				u: px / this.width,  // uv坐标，用于取得纹理像素
				v: py / this.height
			}	
			return hit_record;
		}
	}


	class HitableList {
		constructor(hitables) {
			this.hitables = hitables
		}

		hit(ray, tmin, tmax) {
			let hit_record = null
			let closest_so_far = tmax
			for (let i = 0; i < this.hitables.length; i++) {
				let temp_rec = this.hitables[i].hit(ray, tmin, closest_so_far)
				if (temp_rec) {
					closest_so_far = temp_rec.t
					hit_record = temp_rec
				}
			}
			return hit_record
		}
	}
	
	
	function deg2rad(d) {
		return d / 180 * Math.PI;
	}


	const objects = new Array();
	function main() {
		let canvas = document.getElementById('canvas0');
		let ctx = canvas.getContext('2d');
		let width = canvas.width
		let height = canvas.height
		let imageData = ctx.getImageData(0, 0, width, height);
		let data = imageData.data;
		let dataUV = new Array(width * height * 2);
		const r = Math.sqrt(3)  // 万花筒的外径
		objects[0] = new Rect(
			[r * Math.cos(deg2rad(150)), r * Math.sin(deg2rad(150)), 0],  // 原点
			[1, 0, 0],                                                      // x
			[0, 0, -1],
			r * Math.sqrt(3), 4, new Metal([0.95, 0.95, 0.95]))
		objects[1] = new Rect(
			[r * Math.cos(deg2rad(30)), r * Math.sin(deg2rad(30)), 0],
			[-1, -Math.sqrt(3), 0], 
			[0, 0, -1],
			r * Math.sqrt(3), 4, new Metal([0.95, 0.95, 0.95]))
		objects[2] = new Rect(
			[r * Math.cos(deg2rad(270)), r * Math.sin(deg2rad(270)), 0],
			[-1, Math.sqrt(3), 0],
			[0, 0, -1],
			r * Math.sqrt(3), 4, new Metal([0.95, 0.95, 0.95]))
		const screenWidth = 4.5;
		const screen = objects[3] = new Rect(
		    [-screenWidth/2, -screenWidth/2, -4.5],
		    [1, 0, 0], 
		    [0, 1, 0],
		    screenWidth,
		    screenWidth,
		    new Lambertian(
		        [1.0, 1.0, 1.0], 
		        new ImageTexture('texture_img')
		    )
		)
		const hitables = new HitableList(objects)
		camera = new Camera()
		for (let i = 0; i < width; i++) {
			console.log(i);
			for (let j = 0; j < height; j++) {
				// 多次射出光线，每次射出的光线都有随机的微小偏差。取每次光线追踪结果的平均值，达到反锯齿的效果。
				const u = (i + Math.random()) / width
				const v = 1 - (j + Math.random()) / height
				ray = camera.getRay(u, v)
				p = ray.point_at_t(2.0)
				const ret = colorWithRecord(ray, hitables, 0);
				const c = ret[0]; let records = ret[1];
				const px = j * width + i
				data[px * 4 + 0] = 255 * c[0]
				data[px * 4 + 1] = 255 * c[1]
				data[px * 4 + 2] = 255 * c[2]
				data[px * 4 + 3] = 255

				// 记录屏幕上的纹理坐标
				function findRecord(records) {
					for (let i = 0; i < records.length; ++i) {
						if (records[i].material == screen.material)
						    return records[i];
					}
					return undefined;
				}
				const mRecord = findRecord(records);
				const u2 = mRecord ? mRecord['u'] : undefined,
					v2 = mRecord ? mRecord['v'] : undefined;
				if (typeof(u2) == 'undefined' || typeof(v2) == 'undefined') {
					// invalid
					dataUV[px * 2 + 0] = -1;
					dataUV[px * 2 + 1] = -1;
				}
				else {
					dataUV[px * 2 + 0] = u2;
					dataUV[px * 2 + 1] = v2;
				}
			}
		}
		console.log(dataUV);
		ctx.putImageData(imageData, 0, 0);
		console.log(window.btoa(dataUV))
	}
</script>

</head>
<body>
<div>
	<h2>光线跟踪技术 练习</h2>
	<h4>万花筒</h4>
	<p>
	输入图像：
	</p>
	<img id='texture_img' src="../../res/star-cloud4.jpg" onload="main()"></img>
	<p>
	输出图像：
	</p>
	<canvas id="canvas0" height="240" width="480">你的浏览器不支持canvas！</canvas>
</div>
</body>
</html>
